"""
《啊哈！算法》读书笔记
首先要在这个队列中找到基准数：k
然后分别设定两个哨兵为队列的头和尾，然后两个往中间走，右边先出发，若找到的数大于基准数，就继续走，若小于则停下。

然后左边的哨兵往右走，若出现的数小于基准数，就继续走，若大于基准数则停下。

此时，两个哨兵交换对应数据，交换完后，继续走，若两个哨兵相遇，停止，此时，将基准数与两个哨兵对应数据交换，基准数归位。

然后以此类推，运用递归的方式，分别对基准数左边和右边的队列进行排序。

"""
def quickSort(li):
    if len(li) < 2:
        return li
    else:
        left,right = 0, len(li)-1
        temp = li[0]
        i,j = left,right
        while i != j:
            while i < j and li[j] >= temp:
                j -= 1
            while i < j and li[i] <= temp:
                i += 1
            if i < j:
                li[i],li[j] = li[j],li[i]

        li[left],li[i] = li[i],li[left]
        return quickSort(li[:i]) + [li[i]] + quickSort(li[i+1:])
  
import unittest

# 测试快速排序算法
class TestQuickSort(unittest.TestCase):

    # 测试用例：空列表
    def test_empty_list(self):
        self.assertEqual(quickSort([]), [])

    # 测试用例：单元素列表
    def test_single_element_list(self):
        self.assertEqual(quickSort([5]), [5])

    # 测试用例：已排序列表
    def test_sorted_list(self):
        self.assertEqual(quickSort([1, 2, 3, 4, 5]), [1, 2, 3, 4, 5])

    # 测试用例：逆序排列列表
    def test_reverse_sorted_list(self):
        self.assertEqual(quickSort([5, 4, 3, 2, 1]), [1, 2, 3, 4, 5])

    # 测试用例：随机列表
    def test_random_list(self):
        import random
        li = [random.randint(0, 100) for _ in range(10)]
        sorted_li = sorted(li)
        self.assertEqual(quickSort(li), sorted_li)

if __name__ == '__main__':
    unittest.main()


